package chapter02;

public class MaxSubArray53 {
    /**
     * 动态规划
     * dp[i] 表示[0~i]必须包括arr[i]的最大值
     * 初始化
     *    dp[0]=num[0]
     *    max=dp[0]
     * 1).dp[i]更新
     *    [0~i]必须包括arr[i]的最大值有两种可能
     *    a.dp[i-1]+num[i]
     *    b.num[i]
     *    dp[i]==b<a?a:b
     * 2).更新max
     *    max=max(max,dp[i])
     */
    public int maxSubArray(int[] nums) {
        if(nums.length<2){
            return nums[0];
        }
        int[] dp=new int[nums.length];
        dp[0]=nums[0];
        int max=dp[0];
        for(int i=1;i<dp.length;i++){
            dp[i]=nums[i]<dp[i-1]+nums[i]?dp[i-1]+nums[i]:nums[i];
            max=Math.max(max,dp[i]);
        }
        return max;
    }

    //根据动态规划改成空间O(1)
    public int maxSubArray1(int[] nums) {
        if(nums.length<2){
            return nums[0];
        }
        int res=nums[0];
        int max=res;
        for(int i=1;i<nums.length;i++){
            res=Math.max(nums[i],res+nums[i]);
            max=Math.max(max,res);
        }
        return max;
    }
}
